COMMENT ⊗   VALID 00010 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1
C00008 00003	  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1
C00013 00004	  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1
C00018 00005	  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1
C00023 00006	  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1
C00029 00007	  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1
C00034 00008	  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1
C00039 00009	  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1
C00043 00010	  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1
C00047 ENDMK
C⊗;
  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1

**** File 1) CONCEP.2[CLS,LSP]/1P/511L
1)	A {\bit generic function\/} is a function object, which, when it is invoked,
1)	is able to designate one out of a set of operations, depending on the
1)	classes of its arguments.  The generic function is said to
1)	{\bit discriminate\/} on the classes of its arguments.
1)	[The following is under discussion:
1)	A generic function is a first-class object in the \CLOS.
1)	It can be used as an argument to {\bf funcall} or {\bf apply} and
1)	stored in the symbol-function cell of a symbol.]
1)	[The following is under discussion:  A generic function is created
1)	using the function {\bf make-generic} or the
1)	macro {\bf defgeneric}. The macro {\bf defgeneric} stores the generic function
1)	in a specified symbol-function cell.]
1)	The operations that are provided by a generic function are defined by
1)	the methods associated with it.
1)	A {\bit method\/} is a function object.  It consists of two
1)	parts: a set of argument
1)	{\bit specializers\/} that is used to determine when it is applicable and a method
1)	function.
1)	%Methods are first-class objects in the \CLOS.
1)	A method can be used as an argument to {\bf funcall} or {\bf apply} and
1)	stored in the symbol-function cell of a symbol.
1)	A method can be defined and associated
1)	with a generic function by using {\bf defmethod} or {\bf add-method}.
1)	[An issue under discussion is whether a generic function must be defined
1)	before any methods can be added to it.]
1)	When a generic function is invoked, the arguments specializers of its
1)	associated methods are used to determine which method function is
1)	invoked.
1)	An {\bit argument specializer\/} is the name of a class or an
1)	individual.
1)	The class of each of the arguments passed to the generic function
1)	is determined and the classes of the arguments are then
1)	compared with the
1)	argument specializers of each of the methods associated with the generic
1)	function.  The method function of the method with the most specific
1)	set of argument specializers that are identical to or more general than
1)	the classes of the arguments is invoked.  The order in which differences
1)	between the classes of the arguments and the arguments specializers are
1)	considered is defined by the
1)	{\bit argument precedence order\/} for the generic function. The relative
1)	specificity of argument specializers is determined by the class lattice.
1)	%The {\bf class precedence list} is used to determine
1)	%which specializer is more specific.
1)	Any individual is always more specific than any class.  There
1)	is a class named {\bf t} that is more general than any other class.  When every
1)	argument specializer in the set of argument specializers for a method is either
1)	unspecified or {\bf t}, the method function for that method is called the
  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1

1)	{\bit default method function\/} of the generic function.
1)	%The precise definition for determining which method of a generic
1)	%function to invoke will be given in section XXX.
1)	\endSection%{Generic Functions and Methods}
1)	\beginSection{Method Selection}
1)	\endSection%{Method Selection}
1)	\beginSection{Method Combination}
1)	[To be written.]
1)	We are currently working to integrate the programmatic ({\bf
1)	run-super}) and declarative ({\bf define-method-combination}) method
1)	combination techniques.  The references to method combination throughout
1)	this document will be further specified in a future draft.
1)	%Methods can be combined by means of the {\bf run-super} construct.
1)	%The {\bf run-super} construct allows a method to specialize a ``super''
1)	%method.
1)	\endSection%{Method Combination}
1)	\beginSection{Meta Objects}
**** File 2) CONCEP.3[CLS,LSP]/1P/511L
2)	\beginsubSection{Introduction to Generic Functions}
2)	Like ordinary Lisp functions, generic functions take arguments, perform
2)	an operation, and perhaps return useful values.  An ordinary function
2)	has a single body of code that is always executed when the function is
2)	called.  The implementation of a generic function varies from call to
2)	call, depending on the class of one or more of the arguments.  An
2)	argument that selects which method or methods to run is called a
2)	specialized argument.  A generic function can have several methods
2)	associated with it, and the class of each specialized argument to the
2)	generic function indicates which method or methods to use.  The generic
2)	function is said to discriminate on the classes of its arguments.
2)	Ordinary functions and generic functions are called with identical
2)	syntax:
2)	  (function-name arguments...)
2)	 
2)	Generic functions are not only syntactically compatible with ordinary
2)	functions; they are semantically compatible as well:
2)	 o They are true functions that can be passed as arguments and used as
2)	   the first argument to FUNCALL and APPLY.   
2)	 o The name of a generic function is in a certain package and can be
2)	   exported if it is part of an external interface.  This allows
2)	   programmers to keep unrelated programs separate.  
2)	Ordinary functions have a single definition; generic functions have a
2)	distributed definition.   The definition of a generic function can be
2)	found in a DEFGENERIC form and a set of DEFMETHOD forms.    A DEFGENERIC
2)	form provides information about the contract of the generic function.
2)	Evaluating these forms produces a generic-function object,
2)	which can be FUNCALL'ed.   Typically a generic-function object is stored
2)	as the function definition of the symbol that is the name of the generic
2)	function.
  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1

2)	When a new DEFGENERIC form is evaluated and the generic function of this
2)	name already exists (that is, the function definition of the first
2)	subform of DEFGENERIC is a generic-function object), the existing
2)	generic-function object is modified.   Evaluating a DEFGENERIC does not
2)	modify any of the methods associated with the generic function.
2)	\endsubSection%{Introduction to Generic Functions}
2)	\beginsubSection{Introduction to Methods}
2)	A DEFMETHOD form contains the code that is to be run when the
2)	specialized arguments to the generic function cause this method to be
2)	selected.   DEFMETHOD creates a method-object.  If a DEFMETHOD form is 
2)	evaluated and the method-object already exists, the new definition 
2)	replaces the old.
2)	Each method has a "specialized" lambda list, which indicates 
2)	which of its arguments are to be used for method selection.  Only
2)	required parameters can be specialized.  [It is still under discussion
2)	whether optional parameters can be specialized.]  A specialized
2)	parameter is a list of (variable-name parameter-specializer), where
2)	parameter-specializer is one of:
2)	   o A user-defined class
2)	   o (QUOTE object)
2)	   o A symbol naming a built-in class corresponding to one of these CL
2)	     types:  
2)	        array               integer          rational
2)	        bit-vector          list             readtable
2)	        character           long-float       sequence
2)	        compiled-function   null             short-float
2)	        complex             number           single-float
2)	        cons                package          string
2)	        double-float        pathname         symbol
2)	        float               random-state     t
2)	        hash-table          ratio            vector
2)	 
2)	Note that a parameter-specializer is a symbol, and cannot be a list
2)	such as (vector single-float).  
2)	Methods can also have arguments not intended to be used for selection;
2)	such parameters are in normal DEFUN syntax.
2)	A method that has only one specialized parameter is called a classical
2)	method.   A method with more than one specialized parameter is a
2)	multi-method.   A method with no specialized parameters is a default
2)	method; it is always available for the generic function, but often
2)	shadowed by a more specific method.   A default method can also have a 
2)	parameter specializer of T; this is the same as if that parameter had no 
2)	specializer.  An individual method is one whose specialized parameter 
2)	is (QUOTE object); this method is selected if the corresponding 
2)	argument to the generic function is EQL to the object.   The parameter
2)	specializer (QUOTE object) is more specific than any other specializer. 
2)	 
2)	Methods can have qualifiers.   If a method has no qualifier it is called
  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1

2)	a primary method.   Some examples of method qualifiers are:  :BEFORE,
2)	:AFTER, and :AROUND.   A :BEFORE method specifies code that runs before
2)	the primary method, and an :AFTER method specifies code that runs after
2)	the primary method.  Method qualifiers give the method combination
2)	procedure a way to distinguish between methods.  
2)	\endsubSection%{Introduction to Methods}
2)	\beginsubSection{Congruent Lambda-lists for all Methods of a Generic Function}
2)	The lambda-list in the DEFGENERIC specifies the "shape" of the generic  
2)	function arguments.  All methods for this generic function must be
2)	congruent with this shape; this implies that the system can determine 
2)	whether a call is syntactically correct.   The rules are: 
2)	[The following is a first approximation of these rules, which need
2)	to be discussed further:]
2)	1.  Each method must have the same number of required arguments. 
2)	2.  Each method must have the same number of &optional arguments, but 
2)	    methods can supply different defaults for &optional arguments. 
2)	3.  If &allow-other-keys is used by one method, all methods must use
2)	    it.   
2)	4.  If &allow-other-keys is not used, each method must allow the same
2)	    number of &key arguments, and these keyword arguments must have
2)	    the same names across methods.  
2)	5.  If &rest is used by one method, all methods must use it. 
2)	6.  The use of &aux need not be consistent across methods.  
2)	The method receives the same arguments that the generic function 
2)	received. 
2)	\endsubSection%{Congruent Lambda-lists for all Methods of a Generic Function}
2)	\endSection%{Generic Functions and Methods}
2)	\beginSection{Method Selection and Combination}
2)	When a generic function is called, it must decide: 
2)	 o  Which method (or methods) to call
2)	 o  The order in which to call the methods
2)	 o  Which value (or values) to return 
2)	 o  If CALL-NEXT-METHOD is used, it is important to know which is the
2)	    "next" method to call. 
2)	These requirements are handled by the following 4-step procedure: 
2)	1.  Select the set of available methods. 
2)	Given a generic function and the arguments to it, the set of available
2)	methods includes all methods for that generic function whose specialized
2)	parameters match their corresponding arguments.     A method's
2)	specialized parameter matches its corresponding argument if:
2)	    o The class of the argument has the class of the specializer as a 
2)	      component class.   
2)	    o Or, the specialized parameter is (QUOTE object) and the argument
2)	      is EQL to the object. 
2)	2.  Sort the available methods into a precedence order. 
2)	To compare the precedence of two methods, examine their parameter
2)	specializers in order from left to right.  (Note that the left to right
2)	precedence order is the default. It can be changed by the
  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1

2)	:ARGUMENT-PRECEDENCE-ORDER option to DEFGENERIC.)  Compare each argument
2)	to the generic function to the corresponding parameter specializers of
2)	the methods. 
2)	The first pair of parameter specializers that are not equal determine
2)	the precedence.  Method X is more specific than method Y if method X's
2)	parameter specializer appears earlier than method Y's parameter specializer
2)	in the class precedence list of the class of the argument.  (Due to the
2)	way the set of available methods is chosen, it is guaranteed that 
2)	the parameter specializers are present in the class precedence list of
2)	the class of the argument.) 
2)	Any unspecialized parameters have an implied type specifier of T.  T is
2)	implied at the very end of each class precedence list, so it is less
2)	specific than any other class.  (QUOTE object) is more specific than any
2)	class.  (If both parameter specializers are quoted objects, they must be
2)	equal or both methods would not be available for this argument.)
2)	The resulting list of available methods is sorted with the most specific
2)	method first and the least specific method at the end.
2)	3.  Apply method combination to the sorted list of methods. 
2)	The method combination technique specified for the generic function receives
2)	the sorted list of available methods and returns a Lisp form.  This form
2)	contains calls to some or all of the methods, and defines the value(s)
2)	to be  returned by the generic function.   The method combination might 
2)	make some of the methods reachable via CALL-NEXT-METHOD, rather than
2)	calling them directly.   
2)	The meaning of the qualifiers of a method is defined entirely by this
2)	step of the procedure.  Method qualifiers give the method combination 
2)	procedure a way to distinguish between methods.   
2)	See "DAEMON Method Combination" for a description of how the default
2)	method combination chooses methods to call, makes some methods available
2)	by CALL-NEXT-METHOD, and defines the values to be returned by the
2)	generic function. 
2)	The DEFINE-METHOD-COMBINATION facility allows the programmer to
2)	customize this step of the procedure without needing to consider what 
2)	happens in the other steps.   (The other steps of the procedure can be
2)	customized using meta-objects.)
2)	4.  Consider the resulting Lisp form.
2)	In the simplest implementation, the generic function simply evaluates
2)	the form.  In practice, this is too inefficient and most implementations
2)	do not execute this entire procedure every time a generic function is
2)	called.  Instead they employ a variety of optimizations such as 
2)	precomputation into tables, compilation, and/or caching to speed things
2)	up.  Some illustrative examples (not exhaustive):
2)	  o Use a hash table keyed by the class of the arguments.
2)	  o Compile the Lisp form and save the resulting compiled-function.
2)	  o Recognize the Lisp form as an instance of a pattern of control structure
2)	    and substitute a closure of a function that implements that structure.
2)	The Lisp form serves as a more general interface.  For example, a tool that
2)	determines which methods are called and presents them to the user works by
  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1

2)	going through the above procedure and then analyzing the form to determine
2)	which methods it calls, instead of evaluating it.
2)	\endSection%{Method Selection and Combination}
2)	\beginSection{DAEMON Method Combination}
2)	The default type of method combination is called :DAEMON.  A method's
2)	type is determined by the qualifier arguments to DEFMETHOD.  The 
2)	following method types are recognized by :DAEMON method combination:
2)	primary  These methods have no qualifiers in the DEFMETHOD form.   They
2)	         are the most common type of method.   CALL-NEXT-METHOD may
2)	         be used in a primary method.  
2)	:BEFORE :BEFORE methods have the keyword :BEFORE as their only DEFMETHOD 
2)	        qualifier argument.  They are used to specify code that is to
2)	        run before the primary method. 
2)	:AFTER  :AFTER methods have the keyword :AFTER as their only DEFMETHOD
2)	        qualifier argument.  They are used to specify code that is to
2)	        run after the primary method. 
2)	:AROUND :AROUND methods have the keyword :AROUND as their only 
2)	        DEFMETHOD qualifier argument.  Inside 
2)	        the body of an :AROUND method, the function CALL-NEXT-METHOD can
2)	        be used to immediately call the "next method" (see below). 
2)	        When the next method returns, the :AROUND method can execute
2)	        more code, perhaps based on the returned value(s).   
2)	The semantics of :DAEMON method combination are:
2)	  o If there are any :AROUND methods, the most specific :AROUND
2)	    method is executed, and supplies the value(s) of the generic
2)	    function.  
2)	  o If an :AROUND method uses CALL-NEXT-METHOD, the next most
2)	    specific :AROUND method is executed, if one is available.  
2)	    If there are no :AROUND methods at all, or if CALL-NEXT-METHOD 
2)	    is done by the least specific :AROUND method, the other methods are 
2)	    executed in the following way: 
2)	       o All the :BEFORE methods are executed, in most-specific-first
2)	         order. 
2)	       o The most specific primary method is executed, and supplies the
2)	         value(s) returned by the generic function (or by
2)	         CALL-NEXT-METHOD in the lease specific :AROUND method). 
2)	         If it does CALL-NEXT-METHOD, 
2)	         the second most specific primary method is executed, and so on
2)	         until there are no more primary methods.   An error is
2)	         signalled if CALL-NEXT-METHOD is used and there is no primary
2)	         method available to call. 
2)	       o All the :AFTER methods are executed in most-specific-last order.
2)	Special Notes:
2)	In :DAEMON combination, if there are any available methods at all, then 
2)	there must be an available primary method or there is no method to
2)	produce the value(s).   In such cases an error is signalled.
2)	When all of the methods are primary methods:   If CALL-NEXT-METHOD
2)	is not used, the classical method-shadowing behavior is obtained.  If
  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1

2)	CALL-NEXT-METHOD is used, the effect is the same as RUN-SUPER in
2)	LOOPS.  
2)	It should be noted that all :AROUND methods run before any primary
2)	methods run.  Thus a less specific :AROUND method runs before a more
2)	specific primary method.   
2)	This section has described the use of the default :DAEMON method
2)	combination type, and the default order, which is :MOST-SPECIFIC-FIRST.
2)	You can use the :METHOD-COMBINATION option to DEFGENERIC and supply an
2)	argument of :MOST-SPECIFIC-LAST to change the order of methods.
2)	:MOST-SPECIFIC-LAST reverses the order of the primary methods.  The
2)	order of the :BEFORE, :AFTER, and :AROUND methods is not changed, and it
2)	is still the case that all of the :AROUND methods are executed before
2)	any primary methods.
2)	\endSection%{DAEMON Method Combination}
2)	\beginSection{Determining the Class Precedence List}
2)	A class precedence list is used in several ways.  The method selection 
2)	and combination process uses the class precedence list to order methods
2)	from most specific to least specific.   When one class has several 
2)	components, a more specific class can override options declared in the 
2)	DEFCLASS form of a less specific class.    
2)	\beginsubSection{Rules for Determining Class Precedence}
2)	The DEFCLASS forms of a class and each of its super-classes set 
2)	local constraints on the ordering of classes.  When a class is built
2)	from super-classes, all of the local constraints of the class and its
2)	super-classes are taken into account, and an ordering is computed that
2)	satisfies all of these constraints.  In other words, the DEFCLASS
2)	forms specify partial orderings, which must be merged into one total
2)	ordering.
2)	Three rules govern the ordering of classes:
2)	1. A class always precedes its own super-classes.
2)	2. The local ordering of super-classes within each DEFCLASS form is
2)	preserved. 
2)	3. Duplicate classes are eliminated from the ordering; if a class
2)	appears more than once, it is placed as close to the beginning of the
2)	ordering as possible, while still obeying the other rules.
2)	\endsubSection%{Rules for Determining Class Precedence}
2)	\beginsubSection{Constructing a Tree of Classes}
2)	One way to merge the partial orderings is to construct a tree 
2)	of classes.   The root of the tree is the class for which we are
2)	computing a class precedence list.   From that root, the class's
2)	super-classes are added from left to right, as they appear in the
2)	DEFCLASS form.   
2)	The ordering is determined by walking through the tree in depth-first
2)	left-to-right order, and adding each class to the ordering if it fits
2)	the constraints of the three rules.  If the class can be placed next in
2)	the ordering without transgressing one of the three rules, it is added.
2)	If adding it would transgress a rule, that class is skipped.  If the end
2)	of the tree is reached and some classes have not yet been placed in the
  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1

2)	ordered list, we walk through the tree again, continuing to apply the
2)	three rules to the remaining classes and add them to the ordering.  In
2)	complicated programs, it is conceivable that we could walk through the
2)	tree several times.
2)	If some classes cannot be ordered according to the rules, an error is 
2)	signalled to inform the user of the conflicting constraints.   An
2)	example of this is given at the end of this section. 
2)	Here is an example of determining a class precedence list.
2)	The classes are defined: 
2)	(defclass pie (apple cinnamon) ())
2)	(defclass apple (fruit) ())
2)	(defclass cinnamon (spice) ())
2)	(defclass fruit (food) ())
2)	(defclass spice (food) ())
2)	(defclass food () ())
2)	The tree of classes for PIE is:
2)	                 pie
2)	                /   \
2)	            apple  cinnamon
2)	             /         \
2)	          fruit      spice
2)	            /           \
2)	          food         food      
2)	The list begins with PIE.  We continue, adding APPLE and 
2)	FRUIT.   So far, the (incomplete) ordered list is: 
2)	     (pie apple fruit 
2)	The next class is FOOD, but we cannot place it next in the ordering
2)	because doing so would transgress the rule that a class always precedes
2)	its own super-classes.   If placed next, FOOD would precede SPICE,
2)	and we know that SPICE must precede FOOD.    Thus we skip
2)	FOOD and continue through the tree.    Because FOOD appears
2)	later in the tree, we pick it up then.   The ordering is now complete:
2)	     (pie apple fruit cinnamon spice food)
2)	\endsubSection%{Constructing a Tree of Classes}
2)	\beginsubSection{When Several Orderings are Possible}
2)	In many cases, the three rules define a single valid ordering of
2)	classes.    In other cases, several orderings are valid.  For example, 
2)	suppose PIE class and its super-classes are defined as follows:
2)	(defclass pie (apple cinnamon) ())
2)	(defclass apple (fruit) ())
2)	(defclass cinnamon (spice) ())
2)	(defclass fruit () ())
2)	(defclass spice () ())
2)	The tree-walk results in the ordering: 
2)	     (pie apple fruit cinnamon spice) 
2)	In fact, there are two additional valid orderings: 
2)	     (pie apple cinnamon fruit spice) 
2)	     (pie apple cinnamon spice fruit)
  1) CONCEP.2[CLS,LSP] and 2) CONCEP.3[CLS,LSP]	10-27-86 18:01	pages 1,1

2)	A well-conceived program must not depend on any one of those 
2)	orderings, but should work equally well under any of them.   For 
2)	example, if your program depends on SPICE preceding FRUIT in
2)	the ordering for PIE, you should make that constraint explicit by 
2)	including those two classes in the list of super-classes in the 
2)	DEFCLASS form for PIE.
2)	\endsubSection%{When Several Orderings are Possible}
2)	\beginsubSection{Conflicting Class Definitions}
2)	It is possible to write a set of class definitions that cannot be 
2)	ordered using the rules.   For example: 
2)	(defclass new-class (fruit apple) ())
2)	(defclass apple (fruit) ())
2)	FRUIT must precede APPLE because the local ordering of super-classes is
2)	preserved.  APPLE must precede FRUIT because a class always precedes its
2)	own super-classes.  When this situation occurs, an error is signalled
2)	when the system tries to compute the class precedence list.  At that
2)	point you can redefine one or more of the classes to resolve the
2)	problem, presumably by changing the local order of super-classes to
2)	resolve the conflict.
2)	Note the following example, which appears at first glance to be a
2)	conflicting set of definitions: 
2)	(defclass pie (apple cinnamon) ())
2)	(defclass pastry (cinnamon apple) ())
2)	The ordering for PIE is:  (pie apple cinnamon)	
2)	The ordering for PASTRY is:  (pastry cinnamon apple)
2)	There is no problem with the fact that APPLE precedes CINNAMON in the
2)	ordering of the super-classes of PIE, but not in the ordering for
2)	PASTRY.    However, you cannot build a new class that has both PIE and
2)	PASTRY as super-classes .
2)	\endsubSection%{Conflicting Class Definitions}
2)	\endSection%{Determining the Class Precedence List}
2)	\beginSection{Declaration Method Combination}
2)	We are currently working to integrate the programmatic ({\bf run-super})
2)	and declarative ({\bf define-method-combination}) method combination
2)	techniques.   This is still under discussion. 
2)	\endSection%{Declarative Method Combination}
2)	\beginSection{Meta Objects}
***************